package com.lw.leetcode.tree.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1032. 字符流
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/2 10:49
 */
public class StreamChecker {

    public static void main(String[] args) {
        String[] arr = {"a"};
        StreamChecker test = new StreamChecker(arr);

        boolean a = test.query('a');
        System.out.println(a);


    }

    private List<Integer> list = new ArrayList<>();
    private Node root = new Node();

    public StreamChecker(String[] words) {
        for (String word : words) {
            add(root, word.toCharArray(), word.length() - 1);
        }
    }

    public boolean query(char letter) {
        int v = letter - 'a';
        list.add(v);
        int st = -1;
        if (list.size() >= 200) {
            st = list.size() - 201;
        }
        return find(root, list.size() - 1, st);
    }

    private boolean find(Node node, int index, int st) {
        if (node != null && node.end) {
            return true;
        }
        if (index == st || node == null) {
            return false;
        }
        int v = list.get(index);
        Node no = node.arr[v];
        return find(no, index - 1, st);
    }

    private void add(Node node, char[] chars, int index) {
        if (index  == -1) {
            node.end = true;
            return;
        }
        int v = chars[index] - 'a';
        Node[] arr = node.arr;
        if (arr == null) {
            arr = new Node[26];
            node.arr = arr;
        }
        if (arr[v] == null) {
            arr[v] = new Node();
        }
        add(arr[v], chars, index - 1);
    }

    private static class Node {
        private Node[] arr;
        private boolean end;
    }

}
